package com.zhj.algorithm.search.str;

public class KMPSearch implements StrSearch {

    @Override
    public int search(String A, String B) {
        if (A == null || A.length() == 0 || B == null || B.length() == 0 || A.length() < B.length()) {
            return -1;
        }
        int[] next = getNext(B);
        int j = 0;
        for (int i = 0; i < A.length(); i++) {
            while (j > 0 && A.charAt(i) != B.charAt(j)) {
                j = next[j];
            }
            if (A.charAt(i) == B.charAt(j)) {
                j++;
            }
            if (j == B.length()) {
                return i - B.length() + 2;
            }
        }
        return -1;
    }

    private int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        int j = 0;
        for (int i = 2; i < pattern.length(); i++) {
            while (j != 0 && pattern.charAt(j) != pattern.charAt(i-1)) {
                j = next[j];
            }
            if (pattern.charAt(j) == pattern.charAt(i-1)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

}
